#include <iostream>
using namespace std;
const int MOD = 9907;

int main()
{
	int t = 0;
	cin >> t;
	while( t-- )
	{
		int a = 0, b = 0;
		cin >> a >> b;

		int p[32] = {0};
		int count = 0;
		while( b > 0 )
		{
			p[count++] = b % 2;
			b = b / 2;
		}

		int c[32] = {0};
		c[0] = a % MOD;
		for( int i = 1; i < count; i++ )
		{
			c[i] = (c[i - 1] * c[i - 1]) % MOD;
		}
		c[count - 1] = c[count - 1] % MOD;

		int r = 1;
		for( int i = 0; i < count; i++ )
		{
			if( r > MOD ) r = r % MOD;
			if( p[i] )
			{
				r *= c[i];
			}
		}

		cout << r % MOD << endl;


	}
	return 0;
}
